package leecode

func exist(board [][]byte, word string) bool {
	path := make([][]bool, len(board)) //记录访问的路径
	for i := 0; i < len(path); i++ {
		path[i] = make([]bool, len(board[i]))
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[i]); j++ {
			if backtracking1(board, path, word, 0, i, j) {
				//只要有一条符合路径即可
				return true
			}
		}
	}
	return false
}

func backtracking1(board [][]byte, path [][]bool, word string, pathLength, row, column int) bool {
	//递归终止条件
	if pathLength == len(word) {
		return true
	}
	//限制边界
	if row < 0 || row >= len(board) || column < 0 || column >= len(board[0]) {
		return false
	}
	//不允许路径重复 , 检测是否符合条件
	if path[row][column] || board[row][column] != word[pathLength] {
		return false
	}
	path[row][column] = true
	//四个方向
	res := backtracking1(board, path, word, pathLength+1, row-1, column) ||
		backtracking1(board, path, word, pathLength+1, row+1, column) ||
		backtracking1(board, path, word, pathLength+1, row, column+1) || backtracking1(board, path, word, pathLength+1, row, column-1)
	//回溯
	path[row][column] = false
	return res
}
